#ifndef DIFF_UTIL_H
#define DIFF_UTIL_H

#include <vector>
#include <memory>
#include <functional>
#include <algorithm>
#include <stack>
#include <unordered_set>
#include <unordered_map>

// DiffUtil - Myers diff algorithm implementation matching Android DiffUtil
template<typename T>
class DiffUtil {
public:
    // Diff operation types
    enum class OpType {
        INSERT,
        REMOVE,
        MOVE,
        CHANGE,
        NONE
    };
    
    // Single diff operation
    struct DiffOp {
        OpType type;
        int oldPos;
        int newPos;
        int count;
        void* payload;
        
        DiffOp(OpType t, int old, int newP, int c, void* p = nullptr)
            : type(t), oldPos(old), newPos(newP), count(c), payload(p) {}
    };
    
    // Callback interface for item comparison
    class ItemCallback {
    public:
        virtual ~ItemCallback() = default;
        virtual bool areItemsTheSame(const T& oldItem, const T& newItem) const = 0;
        virtual bool areContentsTheSame(const T& oldItem, const T& newItem) const = 0;
        virtual void* getChangePayload(const T& oldItem, const T& newItem) const {
            return nullptr;
        }
    };
    
    // Result of diff calculation
    class DiffResult {
    private:
        std::vector<DiffOp> operations_;
        
    public:
        void addOp(const DiffOp& op) {
            operations_.push_back(op);
        }
        
        const std::vector<DiffOp>& getOperations() const {
            return operations_;
        }
        
        // Dispatch updates to callbacks
        void dispatchUpdatesTo(
            std::function<void(int, int)> onInserted,
            std::function<void(int, int)> onRemoved,
            std::function<void(int, int, void*)> onChanged,
            std::function<void(int, int)> onMoved) const {
            
            // Apply operations in correct order
            for (const auto& op : operations_) {
                switch (op.type) {
                    case OpType::INSERT:
                        if (onInserted) onInserted(op.newPos, op.count);
                        break;
                    case OpType::REMOVE:
                        if (onRemoved) onRemoved(op.oldPos, op.count);
                        break;
                    case OpType::CHANGE:
                        if (onChanged) onChanged(op.oldPos, op.count, op.payload);
                        break;
                    case OpType::MOVE:
                        if (onMoved) onMoved(op.oldPos, op.newPos);
                        break;
                    default:
                        break;
                }
            }
        }
    };
    
private:
    // Snake in Myers algorithm
    struct Snake {
        int startX;
        int startY;
        int endX;
        int endY;
        bool reverse;
        
        Snake(int sx, int sy, int ex, int ey, bool r = false)
            : startX(sx), startY(sy), endX(ex), endY(ey), reverse(r) {}
            
        int size() const {
            return std::max(endX - startX, endY - startY);
        }
    };
    
    // Range for diff calculation
    struct Range {
        int oldStart;
        int oldEnd;
        int newStart;
        int newEnd;
        
        Range(int os, int oe, int ns, int ne)
            : oldStart(os), oldEnd(oe), newStart(ns), newEnd(ne) {}
            
        int oldSize() const { return oldEnd - oldStart; }
        int newSize() const { return newEnd - newStart; }
    };
    
    // Calculate Myers diff
    static std::vector<Snake> calculateDiff(
        const std::vector<T>& oldList,
        const std::vector<T>& newList,
        const ItemCallback& callback,
        int oldStart, int oldEnd,
        int newStart, int newEnd) {
        
        std::vector<Snake> snakes;
        
        int oldSize = oldEnd - oldStart;
        int newSize = newEnd - newStart;
        
        if (oldSize == 0 && newSize == 0) {
            return snakes;
        }
        
        if (oldSize == 0) {
            // All insertions
            snakes.emplace_back(oldStart, newStart, oldStart, newEnd);
            return snakes;
        }
        
        if (newSize == 0) {
            // All deletions
            snakes.emplace_back(oldStart, newStart, oldEnd, newStart);
            return snakes;
        }
        
        // Myers algorithm implementation
        int max = (oldSize + newSize + 1) / 2;
        std::vector<int> forward(2 * max + 1);
        std::vector<int> backward(2 * max + 1);
        
        // Find middle snake
        for (int d = 0; d <= max; d++) {
            // Forward search
            for (int k = -d; k <= d; k += 2) {
                int x, y;
                bool removal = (k == -d || (k != d && forward[k - 1 + max] < forward[k + 1 + max]));
                
                if (removal) {
                    x = forward[k + 1 + max];
                } else {
                    x = forward[k - 1 + max] + 1;
                }
                
                y = x - k;
                int startX = x;
                int startY = y;
                
                // Extend snake
                while (x < oldSize && y < newSize &&
                       callback.areItemsTheSame(oldList[oldStart + x], newList[newStart + y])) {
                    x++;
                    y++;
                }
                
                forward[k + max] = x;
                
                if (x >= oldSize && y >= newSize) {
                    snakes.emplace_back(startX + oldStart, startY + newStart,
                                       x + oldStart, y + newStart);
                    return snakes;
                }
            }
            
            // Backward search
            for (int k = -d; k <= d; k += 2) {
                int x, y;
                bool removal = (k == -d || (k != d && backward[k - 1 + max] > backward[k + 1 + max]));
                
                if (removal) {
                    x = backward[k + 1 + max];
                } else {
                    x = backward[k - 1 + max] - 1;
                }
                
                y = x - k;
                int endX = x;
                int endY = y;
                
                // Extend snake backward
                while (x > 0 && y > 0 &&
                       callback.areItemsTheSame(oldList[oldStart + x - 1], newList[newStart + y - 1])) {
                    x--;
                    y--;
                }
                
                backward[k + max] = x;
                
                if (x <= 0 && y <= 0) {
                    snakes.emplace_back(x + oldStart, y + newStart,
                                       endX + oldStart, endY + newStart, true);
                    return snakes;
                }
            }
        }
        
        return snakes;
    }
    
    // Convert snakes to operations
    static void snakesToOps(
        const std::vector<T>& oldList,
        const std::vector<T>& newList,
        const std::vector<Snake>& snakes,
        const ItemCallback& callback,
        DiffResult& result) {
        
        int oldPos = 0;
        int newPos = 0;
        
        for (const auto& snake : snakes) {
            // Handle deletions
            if (snake.startX > oldPos) {
                result.addOp(DiffOp(OpType::REMOVE, oldPos, -1, snake.startX - oldPos));
            }
            
            // Handle insertions
            if (snake.startY > newPos) {
                result.addOp(DiffOp(OpType::INSERT, -1, newPos, snake.startY - newPos));
            }
            
            // Handle matches (check for content changes)
            for (int i = 0; i < snake.size(); i++) {
                int oldIdx = snake.startX + i;
                int newIdx = snake.startY + i;
                
                if (oldIdx < static_cast<int>(oldList.size()) && 
                    newIdx < static_cast<int>(newList.size())) {
                    
                    if (!callback.areContentsTheSame(oldList[oldIdx], newList[newIdx])) {
                        void* payload = callback.getChangePayload(oldList[oldIdx], newList[newIdx]);
                        result.addOp(DiffOp(OpType::CHANGE, oldIdx, newIdx, 1, payload));
                    }
                }
            }
            
            oldPos = snake.endX;
            newPos = snake.endY;
        }
        
        // Handle remaining deletions
        if (oldPos < static_cast<int>(oldList.size())) {
            result.addOp(DiffOp(OpType::REMOVE, oldPos, -1, oldList.size() - oldPos));
        }
        
        // Handle remaining insertions
        if (newPos < static_cast<int>(newList.size())) {
            result.addOp(DiffOp(OpType::INSERT, -1, newPos, newList.size() - newPos));
        }
    }
    
    // Detect moves (requires T to be hashable)
    template<typename U = T>
    static typename std::enable_if<std::is_same<U, T>::value>::type
    detectMoves(
        const std::vector<T>& oldList,
        const std::vector<T>& newList,
        const ItemCallback& callback,
        DiffResult& result) {
        
        // Build position maps (requires std::hash specialization for T)
        std::unordered_map<size_t, int> oldPositions;
        std::unordered_map<size_t, int> newPositions;
        
        std::hash<T> hasher;
        
        for (size_t i = 0; i < oldList.size(); i++) {
            oldPositions[hasher(oldList[i])] = i;
        }
        
        for (size_t i = 0; i < newList.size(); i++) {
            newPositions[hasher(newList[i])] = i;
        }
        
        // Detect moves
        std::vector<DiffOp> moves;
        for (const auto& op : result.getOperations()) {
            if (op.type == OpType::REMOVE) {
                for (int i = 0; i < op.count; i++) {
                    int oldIdx = op.oldPos + i;
                    if (oldIdx < static_cast<int>(oldList.size())) {
                        size_t hash = hasher(oldList[oldIdx]);
                        auto it = newPositions.find(hash);
                        if (it != newPositions.end()) {
                            moves.emplace_back(OpType::MOVE, oldIdx, it->second, 1);
                        }
                    }
                }
            }
        }
        
        // Add move operations
        for (const auto& move : moves) {
            result.addOp(move);
        }
    }
    
public:
    // Main diff calculation method
    static DiffResult calculateDiff(
        const std::vector<T>& oldList,
        const std::vector<T>& newList,
        const ItemCallback& callback,
        bool detectMovesFlag = true) {
        
        DiffResult result;
        
        if (oldList.empty() && newList.empty()) {
            return result;
        }
        
        if (oldList.empty()) {
            result.addOp(DiffOp(OpType::INSERT, -1, 0, newList.size()));
            return result;
        }
        
        if (newList.empty()) {
            result.addOp(DiffOp(OpType::REMOVE, 0, -1, oldList.size()));
            return result;
        }
        
        // Calculate diff
        auto snakes = calculateDiff(oldList, newList, callback,
                                   0, oldList.size(),
                                   0, newList.size());
        
        // Convert to operations
        snakesToOps(oldList, newList, snakes, callback, result);
        
        // Detect moves (only if T is hashable and flag is set)
        if (detectMovesFlag) {
            try {
                detectMoves(oldList, newList, callback, result);
            } catch (...) {
                // If T is not hashable, skip move detection
            }
        }
        
        return result;
    }
};

// Lambda-based ItemCallback implementation
template<typename T>
class LambdaItemCallback : public DiffUtil<T>::ItemCallback {
private:
    std::function<bool(const T&, const T&)> itemsSame_;
    std::function<bool(const T&, const T&)> contentsSame_;
    std::function<void*(const T&, const T&)> changePayload_;
    
public:
    LambdaItemCallback(
        std::function<bool(const T&, const T&)> itemsSame,
        std::function<bool(const T&, const T&)> contentsSame,
        std::function<void*(const T&, const T&)> changePayload = nullptr)
        : itemsSame_(itemsSame),
          contentsSame_(contentsSame),
          changePayload_(changePayload) {}
    
    bool areItemsTheSame(const T& oldItem, const T& newItem) const override {
        return itemsSame_(oldItem, newItem);
    }
    
    bool areContentsTheSame(const T& oldItem, const T& newItem) const override {
        return contentsSame_(oldItem, newItem);
    }
    
    void* getChangePayload(const T& oldItem, const T& newItem) const override {
        return changePayload_ ? changePayload_(oldItem, newItem) : nullptr;
    }
};

#endif // DIFF_UTIL_H